package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * FlipMatchVoyage
 * <p>
 * 971. 翻转二叉树以匹配先序遍历
 *
 * @author: lupeng6
 * @create: 2021/5/7 15:06
 */
public class FlipMatchVoyage {

    public static void main(String[] args) {

    }

    private List<Integer> answer = new ArrayList<>();

    private int index = 0;

    private int[] voyage;


    /**
     * 深度优先进行遍历
     *
     * @author lupeng6
     * @date 2021/5/7 15:07
     */
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        if (root == null) {
            return answer;
        }
        dfs(root);
        if (!answer.isEmpty() && answer.get(0) == -1) {
            answer.clear();
            answer.add(-1);
        }
        return answer;
    }


    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.val != voyage[index++]) {
            answer.clear();
            answer.add(-1);
            return;
        }
        if (index < voyage.length && node.left != null && node.left.val != voyage[index]) {
            answer.add(node.val);
            dfs(node.right);
            dfs(node.left);
        } else {
            dfs(node.left);
            dfs(node.right);
        }

    }
}
